package JavaCode.contest.weekly.n201_300.n282;

import utils.Parse;

import java.util.Arrays;

/**
 * @author mikusugar
 */
public class N4 {

    public static void main(String[] args) {
        System.out.println(new N4().minimumFinishTime(
                Parse.toIntTwoArr("[[601,6],[388,19],[902,17],[405,26],[104,18],[735,12],[146,29],[379,4],[125,6],[448,23],[446,29],[15,30],[827,26],[406,6],[686,11],[655,15],[192,22],[626,29],[182,15],[447,4],[343,12],[958,27],[564,21],[460,16],[207,12],[318,3],[938,28],[185,13],[760,11],[144,12],[432,7],[122,28],[292,11],[971,27],[63,24],[350,23],[401,24],[214,19],[429,7],[245,6],[576,18],[254,30],[508,5],[719,16],[627,27],[480,5],[515,24],[257,26],[90,28],[70,25],[516,29],[365,18],[333,10],[168,6],[901,6],[820,4],[739,16],[636,2],[63,2],[674,12],[489,25],[226,16],[830,29],[284,26],[519,2],[678,28],[836,30],[487,28],[359,16],[325,11],[903,14],[301,30],[926,20],[167,23],[890,14],[355,6],[845,22],[20,26],[946,13],[798,27],[479,23],[472,9],[64,24],[700,30],[492,10],[950,5],[690,6],[587,2],[55,21],[634,13],[745,4],[406,6],[320,30],[444,11],[121,9],[416,9],[707,20],[745,26],[598,11],[35,24],[434,26],[642,12],[648,11],[901,12],[592,23],[939,6],[727,14],[706,12],[917,29],[47,25],[455,24],[359,2],[579,9],[116,4],[328,25],[818,5],[509,17],[631,7],[489,19],[249,17],[155,17],[632,27],[954,28],[751,28],[252,5],[847,2],[629,4],[408,14],[949,26],[69,20],[382,25],[145,10],[341,13],[907,22],[417,24],[448,29],[95,24],[653,21],[594,26],[270,26],[175,24],[973,3],[27,16],[165,7],[45,7],[775,17],[779,20],[467,26],[945,14],[877,29],[192,26],[519,29],[830,30],[662,8],[238,17],[272,30],[436,5],[201,10],[705,29],[361,30],[728,29],[322,30],[376,4],[503,8],[437,12],[650,29],[219,26],[404,20],[752,23],[901,8],[622,7],[468,5],[352,28],[174,8],[727,4],[612,4],[900,29],[598,18],[227,18],[339,9],[854,23],[339,2],[535,22],[122,6],[364,16],[153,27],[35,26],[865,25]]")
                , 458, 861
        ));
    }

    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        long[] dp = new long[numLaps + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int[] tire : tires) {
            dp[1] = Math.min(dp[1], tire[0]);
            long now = tire[0];
            for (int k = 2; k <= numLaps; k++) {
                long pow = (long) Math.pow(tire[1], k - 1);
                if (pow >= Integer.MAX_VALUE) break;
                now += tire[0] * pow;
                if (now >= Integer.MAX_VALUE) break;
                dp[k] = Math.min(dp[k], now);
            }
        }
        for (int i = 2; i <= numLaps; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j] + dp[j] + changeTime);
            }
        }
        return (int) dp[numLaps];
    }


}
